CS 5010: Problem Set 5

Out: Monday, October 13, 2014

Due: Monday, October 20, 2014 at 600pm local time.

The goal of this problem set is to help you design and use multiply-recursive and mutually-recursive data definitions, and to give you practice using the list abstractions and HOFC.

Remember that you must follow the design recipe.

You must use DrScheme's HtDP Intermediate Student Language with Lambda.

As usual, the rubric for` grading is here. You should also refer to the more detailed guidelines here.

Required Exercise

1. The canvas starts empty. Its size is 400 by 400.
2. Nodes of the tree are rendered as green outline squares of a fixed size. The default value for the size (length of the side) is 20, but your system should allow you to change the size for the next run by changing a single line of your code. You can select a node by clicking on it, as in previous problems. Selected nodes are displayed as green solid squares. Clicking on a node selects only the node, not its sons subtree. If the mouse is clicked in the overlap of two or more nodes, all the nodes are selected, even if one node is a son or descendant of the other.
3. When the tree is displayed, there should be a straight blue line from the center of a node to the center of each of its sons.
4. When a node is selected, there should be a vertical line displayed at the position where the left edge of a new son would be if it were created. (See the "n" command, below). 3 square-lengths to the left of that node's leftmost son. This delimits the area in which new sons may be created. (See the "n" command, below). If the selected node has no sons, no line should be displayed
5. Dragging a selected node causes the entire tree rooted at that node to be dragged. The relative positions of all the nodes in the subtree should stay the same. It is ok if this action causes some nodes to be moved off the edge of the canvas; if the node is moved again so that they are now back on the canvas, they should reappear in the proper place.
6. When you drag a node, the rectangle should become centered on the mouse position. (That is, we are not doing "smooth dragging" in this problem.
7. Hitting "t" at any time creates a new root node in the center of the top of the canvas. The root appears tangent to the top of the canvas and initially has no sons.
8. Hitting "n" while a node is selected adds a new son, whose center has an x-coordinate two square-lengths to the left of the center of the currently leftmost son, and a y-coordinate 3 square-lengths down from the center of the parent. If a selected node ever moves into a position so that there is no room for the son, it should appear as red solid rather than green, and "n" has no effect. The first son of a node should appear 3 square-lengths down and directly beneath the node. There is room for a new son if it would be placed with the whole square entirely within the canvas. Note that a node should turn red at the same instant that its vertical line disappears off the left edge of the screen.
9. Hitting "d" while a node is selected deletes the node and its whole subtree.
10. Hitting "u" (whether a node is selected or not) deletes every node whose center is in the upper half of the canvas. (If a node is deleted, all of its children are also deleted.)

Here's a small demo. It doesn't demonstrate "u", though, nor does it demonstrate having multiple roots on the screen, sorry.

Your solution should provide the following functions:

initial-world : Any -> World
GIVEN: any value
RETURNS: an initial world.  The given value is ignored.

run :  Any -> World
GIVEN: any value
EFFECT: runs a copy of an initial world
RETURNS: the final state of the world.  The given value is ignored.

world-after-mouse-event : World Number Number Integer Integer MouseEvent -> World
GIVEN: a World, a location, and a MouseEvent
RETURNS: the state of the world as it should be following the given mouse event at that location.

world-after-key-event : World KeyEvent -> World
GIVEN: a World and a key event
RETURNS: the state of the world as it should be following the given key event
 
world-to-roots : World -> ListOf<Node>
GIVEN: a World
RETURNS: a list of all the root nodes in the given world.
 
node-to-center : Node -> Posn
RETURNS: the center of the given node as it is to be displayed on the scene.

node-to-sons : Node -> ListOf<Node>

node-to-selected? : Node -> Boolean

These functions have the purpose statements suggested by their names.

Before you turn in your solution, make sure it passes the tests in ps05-qualification.rkt. As before, download this file, save it in your set05 directory, and run it to qualify your program for grading. Be sure to commit this file to the repository so we know that you've done this correctly. DO NOT TURN IN YOUR SOLUTION UNLESS IT PASSES THE QUALIFICATION TEST! IF YOUR SOLUTION DOES NOT PASS THE QUALIFICATION TEST, WE MAY NOT GRADE IT.

Please download a fresh copy of extras.rkt for this problem set. The new version should print out a header showing a version date. For this problem, be sure the version you have is dated later than Wed Oct 15 13:00:00 2014. When you run your qualification test, if you get a message like "undefined function check-location", it means that your version of extras.rkt is too old and you need to download the latest one.

Hints:

• Follow the design recipe!! If you write good data definitions, and follow the templates, you will be led to a good solution. If you stray from the templates, you will create a mess. If you are following your templates and still creating a mess, try an alternate path. For example, if you are doing structural decomposition on one data type, followed immediately by structural decomposition on another data type, try doing them in the other order.
• The built-in abstraction functions, like map, foldr, and filter, are your friends. Use them wherever it is feasible to do so. As before, you may want to write your functions using explicit recursions, and then rewrite them using the abstractions and higher-order function combination. You will be penalized for recursions in your code that "obviously" could have been replaced by HOFC.
• Most likely you will want to use scene+line from the image library rather than add-line, since the latter changes the dimensions of the image in surprising ways.
• My solution to this problem was about 320 lines, plus tests. Median time on task for this problem for the last two semesters has been right around 20 hours.